Check if word is valid after substitutions¶
Time: O(N); Space: O(N); medium
We are given that the string “abc” is valid.
From any valid string V, we may split V into two pieces X and Y such that X + Y (X concatenated with Y) is equal to V. (X or Y may be empty.) Then, X + “abc” + Y is also valid.
If for example S = “abc”, then examples of valid strings are: “abc”, “aabcbc”, “abcabc”, “abcabcababcc”.
Examples of invalid strings are: “abccba”, “ab”, “cababc”, “bac”.
Return true if and only if the given string S is valid.
Example 1:
Input: s = “aabcbc”
Output: True
Explanation:
We start with the valid string “abc”.
Then we can insert another “abc” between “a” and “bc”, resulting in “a” + “abc” + “bc” which is “aabcbc”.
Example 2:
Input: s = “abcabcababcc”
Output: True
Explanation:
“abcabcabc” is valid after consecutive insertings of “abc”.
Then we can insert “abc” before the last letter, resulting in “abcabcab” + “abc” + “c” which is “abcabcababcc”.
Example 3:
Input: s = “abccba”
Output: False
Example 4:
Input: s = “cababc”
Output: False
Constraints:
1 <= len(S) <= 20000
S[i] is ‘a’, ‘b’, or ‘c’
[1]:
class Solution1(object):
def isValid(self, S):
"""
:type S: str
:rtype: bool
"""
stack = []
for i in S:
if i == 'c':
if stack[-2:] == ['a', 'b']:
stack.pop()
stack.pop()
else:
return False
else:
stack.append(i)
return not stack
[3]:
sol = Solution1()
s = "aabcbc"
assert sol.isValid(s) == True
s = "abcabcababcc"
assert sol.isValid(s) == True
s = "abccba"
assert sol.isValid(s) == False
s = "cababc"
assert sol.isValid(s) == False